package com.yzp.sort;

import java.util.Arrays;

/**
 * Description
 * 计数排序
 *
 * @className: CountingSort
 * @author: yanzhouping
 * @date: 2019/8/15 9:37
 */
public class CountingSort {

    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 1, 5, 3, 5, 64, 6, 9};
        arr = countingSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 计数排序
     *
     * @param array
     * @return
     */
    public static int[] countingSort(int[] array) {
        if (array.length == 0) {
            return array;
        }
        int bias, min = array[0], max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
        bias = 0 - min;
        int[] bucket = new int[max - min + 1];
        Arrays.fill(bucket, 0);
        for (int i = 0; i < array.length; i++) {
            bucket[array[i] + bias]++;
        }
        int index = 0, i = 0;
        while (index < array.length) {
            if (bucket[i] != 0) {
                array[index] = i - bias;
                bucket[i]--;
                index++;
            } else {
                i++;
            }
        }
        return array;
    }
}
